#define _CRT_SECURE_NO_WARNINGS

#include<stdlib.h>
#include<stdio.h>
#include<assert.h>

//typedef struct ListNode
//{
//    int val;
//    struct ListNode* next;
//}ListNode;
//
//ListNode* partition(ListNode* pHead, int x) {
//    // write code here
//    struct ListNode* head = NULL, * cur = pHead;
//    struct ListNode* end1 = pHead;
//    struct ListNode* end2 = head;
//    while (cur)
//    {
//        if (cur->val < x)
//        {
//            if (cur == pHead)
//            {
//                if (end2 == NULL)
//                {
//                    head = end2 = cur;
//                }
//                else
//                {
//                    end2->next = cur;
//                    end2 = end2->next;
//                }                
//                cur = cur->next;
//                end1 = pHead = cur;
//                
//            }
//            else
//            {
//                if (end2 == NULL)
//                {
//                    head = end2 = cur;
//                }
//                else
//                {
//                    end2->next = cur;
//                    end2 = end2->next;
//                }
//                cur = cur->next;            
//                end1->next = cur;
//            }
//        }
//        else
//        {
//            if (cur == pHead)
//            {
//                cur = cur->next;
//            }
//            else
//            {
//                cur = cur->next;
//                if (end1->next != cur)
//                    end1 = end1->next;
//            }
//        }
//    }
//    if (end1 != NULL)
//    {
//        if (end1->next)
//            end1->next = NULL;
//    }
//    if(head == NULL)
//        head = pHead;
//    else
//        end2->next = pHead;
//    return head;
//    /*struct ListNode* head = NULL,*cur = pHead;
//    struct ListNode* end1 = pHead;
//    struct ListNode* end2 = head;
//    if(pHead->val < x)
//    {
//        head = end2 = pHead;
//        cur = cur->next;
//        end1 = pHead = cur;
//    }
//    else
//    {
//        cur = cur->next;
//    }
//    while(cur)
//    {
//        if(cur->val < x)
//        {
//            end2->next = cur;
//            cur = cur->next;
//            end1->next = cur;
//        }
//    }*/
//}
//
//
//int main()
//{
//    ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n1);
//    ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n2);
//    ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n3);
//    ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n4);
//    ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n5);
//    ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n6);
//    //ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    //assert(n7);
//    //ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    //assert(n8);
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = NULL;
//    n4->next = n5;
//    n5->next = n6;
//    n6->next = NULL;
//    n1->val = 6;
//    n2->val = 2;
//    n3->val = 8;
//    n4->val = 1;
//    n5->val = 3;
//    n6->val = 2;
//
//    ListNode* ret = partition(n1, 9);
//
//    while (ret)
//    {
//        printf("%d ", ret->val);
//        ret = ret->next;
//    }
//    return 0;
//}









//typedef struct ListNode 
//{
//    int val;
//    struct ListNode *next;
//}ListNode;
//
//struct ListNode* removeElements(struct ListNode* head, int val) 
//{
//    struct ListNode* newhead = head;
//    while (head != NULL)
//    {
//        if (head->next->val == val)
//        {
//            //struct ListNode* tmp = head->next;
//            head->next = head->next->next;
//            //free(tmp);
//            //tmp = NULL;
//        }
//        else if (head->val == val)
//        {
//            //struct ListNode* tmp = head;
//            head = head->next;
//            //free(tmp);
//        }
//        else
//        {
//            head = head->next;
//        }
//    }
//    return newhead;
//}
//
//void test()
//{
//    ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n1);
//    ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n2);
//    ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n3);
//    ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n4);
//    ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n5);
//    ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n6);
//    ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n7);
//    ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n8);
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = n4;
//    n4->next = n5;
//    n5->next = n6;
//    n6->next = n7;
//    n7->next = n8;
//    n8->next = NULL;
//
//}
//
//
//int main()
//{
//    test();
//
//
//    return 0;
//}



